#include <stdlib.h>
#include <stdio.h>
#include "main.h"


void _recur_create_tree(BiTreeNode * root_p, char * pre_order_seq, int * current_index_p, int num_elements) {
  if (*current_index_p >= num_elements) {
    return;
  }
  root_p->data = pre_order_seq[*current_index_p];
  (*current_index_p)++;
  if (pre_order_seq[*current_index_p] == '#') {
    root_p->leftChild = NULL;
    (*current_index_p)++;
  } else {
    root_p->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    _recur_create_tree(root_p->leftChild, pre_order_seq, current_index_p, num_elements);
  }
  if (pre_order_seq[*current_index_p] == '#') {
    root_p->rightChild = NULL;
    (*current_index_p)++;
  } else {
    root_p->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    _recur_create_tree(root_p->rightChild, pre_order_seq, current_index_p, num_elements);
  }
}

void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements) {
  *root_pp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
  int current_index = 0;
  _recur_create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}


// 递归地销毁由*root指向根节点的树：释放该树所被动态分配的内存空间
void Destroy(BiTreeNode **root)
{
    if(*root!=NULL)
    {
        Destroy(&((*root)->leftChild));
        Destroy(&((*root)->rightChild));
        free(*root);
        *root=NULL;
    }
}


//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL)
    {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL)
    {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL)
    {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

// 请实现此函数
// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode *Search(BiTreeNode *root, DataType x)
{
  BiTreeNode *find=NULL;
  return find;
}

void Visit(DataType item)
{
  printf("%c ", item);
}


